package leetcode;

import java.util.ArrayList;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0084.java
 * @Author : WangRuoyu
 * @Date 2023/11/4 22:46
 */


public class Q0084 {
    public int largestRectangleArea(int[] heights) {
        int res = 0;

        int[] heights2 = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            heights2[i + 1] = heights[i];
        }
        heights2[0] = -1;
        heights2[heights2.length - 1] = -1;

        ArrayList<Integer> stack = new ArrayList<>();
        for (int i = 0; i < heights2.length; i++) {
            while (!stack.isEmpty() && heights2[stack.get(stack.size() - 1)] > heights2[i]) {
                if (stack.size() > 1) {
                    int j = stack.get(stack.size() - 2);
                    int h = heights2[stack.get(stack.size() - 1)];
                    res = Math.max(res, h * (i - j - 1));
                }
                stack.remove(stack.size() - 1);
            }
            stack.add(i);
        }

        return res;
    }

    public static void main(String[] args) {
        Q0084 sl = new Q0084();
        int[] heights = {2, 4};
        System.out.println(sl.largestRectangleArea(heights));
    }
}